package com.topcoder.srm156;

import java.util.LinkedList;

/**
 * Given a board consisting of empty space, walls, and the starting positions 
 * of two players A and B, determine the minimum number of turns it will take 
 * for players A and B to switch positions on the board.
 * 
 * During a turn, one or both players may take a step. A step is defined as a 
 * unit movement up, down, left, right, or in any of the four diagonals. 
 * Players may not step into walls or off the board. Players may never share 
 * the same square at the end of a turn. Players may not cross paths during a 
 * turn. Crossing paths occurs when players A and B switch positions in a single 
 * turn. For example, assume player A is in the upper left corner of the board, 
 * and player B is in the square immediately to his right. Player A may not move 
 * right while player B moves left, since they would be passing each other. 
 * Player A can, however, move right if player B moves in any other direction.
 * 
 * You will be given a String[] board, representing the game board. board will 
 * contain exactly one 'A' and exactly one 'B'; each other character will be 
 * either '.' (empty space), or 'X' (a wall). Your method should return the 
 * minimum number of turns necessary for players A and B to switch positions, 
 * or -1 if this is impossible.
 * 
 * [Algorithm] BFS
 * [Note] Don't push an invalid item into queue, mark a visisted before pushing
 * to queue. Otherwise, could stuck in an endless loop.
 *
 */
public class PathFinding {
	public int minTurns(String[] board) {
		boolean[][][][] visited = new boolean[20][20][20][20];
		LinkedList<State> queue = new LinkedList<State>();
		
		int M = board.length;
		int N = board[0].length();
		int p1x=0, p1y=0, p2x=0, p2y=0;
		for (int i=0; i<M; i++) {
			char[] c = board[i].toCharArray();
			for (int j=0; j<N; j++) {
				if (c[j] == 'A') {
					p1x = i;
					p1y = j;
				}
				else if (c[j] == 'B') {
					p2x = i;
					p2y = j;
				}
				else if (c[j] == 'X') {
					for (int x=0; x<20; x++) {
						for (int y=0; y<20; y++) {
							visited[i][j][x][y] = true;
							visited[x][y][i][j] = true;
						}
					}
				}
			}
		}
		
		queue.add(new State(p1x, p1y, p2x, p2y, 0));
		while (!queue.isEmpty()) {
			State s = queue.removeFirst();
			if (s.x1 == p2x && s.y1 == p2y && s.x2 == p1x && s.y2 == p1y) return s.steps;
			
			for (int x1=s.x1-1; x1<=s.x1+1; x1++) {
				for (int y1=s.y1-1; y1<=s.y1+1; y1++) {
					for (int x2=s.x2-1; x2<=s.x2+1; x2++) {
						for (int y2=s.y2-1; y2<=s.y2+1; y2++) {
							if ((x1 == s.x2 && y1 == s.y2 && x2 == s.x1 && y2 == s.y1) ||
								(x1 == x2 && y1 == y2) ||
								x1 < 0 || x1 >= M || y1 < 0 || y1 >= N ||
								x2 < 0 || x2 >= M || y2 < 0 || y2 >= N ||
								visited[x1][y1][x2][y2]) continue;
							
							visited[x1][y1][x2][y2] = true;
							queue.add(new State(x1, y1, x2, y2, s.steps+1));
						}
					}	
				}
			}
		}
		
		return -1;
	}
	
	private class State {
		int x1, y1, x2, y2;
		int steps;
		public State(int x1, int y1, int x2, int y2, int steps) {
			this.x1 = x1;
			this.y1 = y1;
			this.x2 = x2;
			this.y2 = y2;
			this.steps = steps;
		}
	}
}
